// Package _4_两个链表相交的问题_最难 main
// @Title _4_两个链表相交的问题_最难
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-01-14 16:48
// @Create  2022-01-14 16:48
package main

/**
	给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
	单链表可能有环，也可能没有环

1. 使用哈希表:

2. 使用双指针
	1. 判断两个链表是否有环
	2. 循环遍历两个链表，记录长度，比较两个链表的尾节点是否一样，如果不一样，不想交
	3. 长一点的链表先走差值步，然后短链表开始一起走，内存相同的就是第一个相交节点
*/

type ListNode struct {
	Val  int
	Next *ListNode
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	lenH1, lenH2 := 0, 0
	p1, p2 := headA, headB
	if headA == nil || headB == nil {
		return nil
	}
	for p1 != nil {
		lenH1++
		p1 = p1.Next
	}
	for p2 != nil {
		lenH2++
		p2 = p2.Next
	}
	if lenH1 > lenH2 {
		for i := 0; i < lenH1-lenH2; i++ {
			headA = headA.Next
		}
	} else if lenH1 < lenH2 {
		for i := 0; i < lenH2-lenH1; i++ {
			headB = headB.Next
		}
	}
	for headA != nil && headB != nil {
		if headA == headB {
			return headA
		}
		headA = headA.Next
		headB = headB.Next
	}
	return headA
}
